1272F - Two Bracket Sequences - CodeForces Solution

#include <iostream>
#include <algorithm>
#include <string>
#include <vector>
#include <queue>
#include <set>
#include <map>
#include <functional>
#include <unordered_map>
#include <climits>
#include <unordered_set>
#include <numeric>
#include <sstream>

using namespace std;

typedef long long LL;
typedef pair<int, int> PII;

class CF1272F {
public:
    string solve(const string &s, const string &t) {
        // static short dp[201][201][402] = {0}; // dp[i][j][k] 表示，从 s[i] 和 t[j] 开始，之前 '(' 比 ')' 多 k，最终超序列的最小长度
        vector<int> dp[201][201];
        for (int i = 0; i <= s.size(); i++) {
            for (int j = 0; j <= t.size(); j++) {
                dp[i][j].resize(i + j + 2);
            }
        }

        for (int i = (int) s.size(); i >= 0; i--) {
            for (int j = (int) t.size(); j >= 0; j--) {
                for (int k = i + j; k >= 0; k--) {
                    if (i == s.size() && j == t.size()) {
                        dp[i][j][k] = k;
                        continue;
                    }
                    if (i == s.size()) { // j < t.size()
                        if (t[j] == '(') {
                            dp[i][j][k] = 1 + dp[i][j + 1][k + 1]; // '('
                        } else if (k > 0) {
                            dp[i][j][k] = 1 + dp[i][j + 1][k - 1]; // ')'
                        } else {
                            dp[i][j][k] = 2 + dp[i][j + 1][k]; // "()"
                        }
                        continue;
                    }
                    if (j == t.size()) { // i < s.size()
                        if (s[i] == '(') {
                            dp[i][j][k] = 1 + dp[i + 1][j][k + 1]; // '('
                        } else if (k > 0) {
                            dp[i][j][k] = 1 + dp[i + 1][j][k - 1]; // ')'
                        } else {
                            dp[i][j][k] = 2 + dp[i + 1][j][k]; // "()"
                        }
                        continue;
                    }
                    if (s[i] == '(' && t[j] == '(') {
                        dp[i][j][k] = 1 + dp[i + 1][j + 1][k + 1];
                    } else if (s[i] == ')' && t[j] == ')') {
                        dp[i][j][k] = 2 + dp[i + 1][j + 1][k]; // '(' + ')'
                        if (k > 0 && dp[i][j][k] > 1 + dp[i + 1][j + 1][k - 1]) {
                            dp[i][j][k] = 1 + dp[i + 1][j + 1][k - 1];
                        }
                    } else if (s[i] == ')' && t[j] == '(') {
                        dp[i][j][k] = 1 + dp[i][j + 1][k + 1]; // '('
                        if (k > 0 && dp[i][j][k] > 1 + dp[i + 1][j][k - 1]) {
                            dp[i][j][k] = 1 + dp[i + 1][j][k - 1]; // ')'
                        }
                    } else if (s[i] == '(' && t[j] == ')') {
                        dp[i][j][k] = 1 + dp[i + 1][j][k + 1]; // '('
                        if (k > 0 && dp[i][j][k] > 1 + dp[i][j + 1][k - 1]) {
                            dp[i][j][k] = 1 + dp[i][j + 1][k - 1]; // ')'
                        }
                    }
                }
            }
        }

        stringstream ss;
        int i = 0, j = 0, k = 0;
        while (i < s.size() || j < t.size()) {
//            cout << "i=" << i << ", j=" << j << ", k=" << k << ", dp=" << dp[i][j][k] << ", ss.size()=" << ss.str().size() << ", total=" << ss.str().size() + dp[i][j][k] << endl;
            if (i == s.size()) { // j < t.size()
                if (t[j] == '(') {
                    ss << "(";
                    j++;
                    k++;
                } else if (k > 0) {
                    ss << ")";
                    j++;
                    k--;
                } else {
                    ss << "()";
                    j++;
                }
                continue;
            }
            if (j == t.size()) { // i < s.size()
                if (s[i] == '(') {
                    ss << "(";
                    i++;
                    k++;
                } else if (k > 0) {
                    ss << ")";
                    i++;
                    k--;
                } else {
                    ss << "()";
                    i++;
                }
                continue;
            }
            if (s[i] == '(' && t[j] == '(') {
                ss << "(";
                i++;
                j++;
                k++;
            } else if (s[i] == ')' && t[j] == ')') {
                if (k > 0 && 2 + dp[i + 1][j + 1][k] > 1 + dp[i + 1][j + 1][k - 1]) {
                    ss << ")";
                    i++;
                    j++;
                    k--;
                } else {
                    ss << "()";
                    i++;
                    j++;
                }
            } else if (s[i] == ')' && t[j] == '(') {
                if (k > 0 && 1 + dp[i][j + 1][k + 1] > 1 + dp[i + 1][j][k - 1]) {
                    ss << ")";
                    i++;
                    k--;
                } else {
                    ss << "(";
                    j++;
                    k++;
                }
            } else if (s[i] == '(' && t[j] == ')') {
                if (k > 0 && 1 + dp[i + 1][j][k + 1] > 1 + dp[i][j + 1][k - 1]) {
                    ss << ")";
                    j++;
                    k--;
                } else {
                    ss << "(";
                    i++;
                    k++;
                }
            }
        }
        while (k--) {
            ss << ")";
        }
//        cout << (int)dp[0][0][0] << endl;
        return ss.str();
    }
};

int main() {
    char s[201], t[201];
    scanf("%s%s", s, t);
    printf("%s\n", CF1272F().solve(string(s), string(t)).c_str());
    return 0;
}